package cn.kingshion.recursion;

/**
 * 迷宫走迷宫问题的初级版本
 * 每次路径其实跟我们选取的游戏策略有一定的联系
 */
public class MiGong {
    public static void main(String[] args) {
        //定义一个迷宫，使用二维数组存放
        int[][] map = new int[8][7];
        //设置迷宫的 4 条边界，全部置为 1 ，
        for (int i = 0;i<map[0].length;i++){
            map[0][i] = 1;
            map[map.length-1][i] = 1;
        }
        for (int i = 0;i<map.length;i++){
            map[i][0] = 1;
            map[i][map[0].length-1] = 1;
        }

        //在迷宫中设置障碍，设置的障碍全部用 1 表示
        map[2][2] = 1;
        map[2][1] = 1;
        map[4][1] = 1;
        map[4][2] = 1;
        map[4][3] = 1;
        map[3][4] = 1;
        map[5][5] = 1;

        System.out.println("迷宫初始状态：");
        for (int i=0;i<map.length;i++){
            for (int j = 0;j<map[i].length;j++){
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }

        System.out.println();
        //开始走迷宫
        setWay(map,1,1);

        System.out.println("迷宫成功状态：");
        for (int i=0;i<map.length;i++){
            for (int j = 0;j<map[i].length;j++){
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }

    }

    /**
     * 使用递归回溯法来走迷宫
     * 游戏说明：
     * 1、map 表示地图
     * 2、i 和 j 表示进入迷宫的起始位置
     * 3、定义小球的终点位置，定义为 ：map[map.length-2][map[0].length-2]
     * 4、给定一个游戏规则：
     *      当 map[i][j] 为 0 的时候表示当前路径还没有走过，
     *      当 map[i][j] 为 1 的时候表示为墙或者障碍物 ，
     *      当 map[i][j] 为 2 的时候表示通路可以走，
     *      当 map[i][j] 为 3 的时候表示该点已经走过来，而且走不通
     * 5、在走迷宫的时候定义一个策略：下--->右--->上--->左    如果该点走不通则回溯
     *
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay(int[][]map,int i,int j){
        //如果迷宫的终点已经走通，那么直接返回 true
        if(map[map.length-2][map[map.length-2].length-2] == 2){
            return true;
        }else {
            //如果当前点没有走过 则先置为 2 表示可以走通
            if(map[i][j] == 0){
                map[i][j] = 2;
                //向下走
                if(setWay(map,i+1,j)){
                    return true;
                }else if(setWay(map,i,j+1)){    //向右走
                    return true;
                }else if(setWay(map,i-1,j)){    //向上走
                    return true;
                }else if(setWay(map,i,j-1)){    //向左走
                    return true;
                }else {
                    //说明该点是不通的
                    map[i][j] = 3;
                    return false;
                }
            }else {
                //如果 map[i][j] ！= 0 那么可能为 1，2，3
                return false;
            }
        }
    }

}
